﻿/* 
 * 
 * 数据结构 —— 链表
 * 与数组相似，链表也是一种线性数据结构
 * 链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。
 *
 * 链表有两种类型：单链表和双链表。
 * 
 * 了解单链表和双链表的结构；
 * 1、在单链表或双链表中实现遍历、插入和删除；
 * 2、分析在单链表或双链表中的各种操作的复杂度；
 * 3、在链表中使用双指针技巧（快指针慢指针技巧）；
 * 4、解决一些经典问题，例如反转链表；
 * 5、分析你设计的算法的复杂度；
 * 6、积累设计和调试的经验。
 *
 * 与数组不同，无法在常量时间内访问到单链表中的随机元素
 * 如果想获取第I个元素，必须从头节点逐个遍历
 * 按【索引】来【访问元素】 平均时间复杂度为O（N）时间，其中是N是链表的长度
 * 
 * 添加操作
 * 1.使用给定值【初始化】新节点Cur
 * 2.将Cur节点的next字段【引用】到Prev节点的下一个Next节点
 * 3.将Prev节点的next字段【引用】到Cur节点上
 * 【注意】插入新节点的需要的时间复杂度为O(1),非常高效
 * 
 * 开头添加节点
 * 1.初始化一个新结点 Cur ；
 * 2.将新结点【引用到】到我们的原始头结点 Head
 * 3.将 Cur 指定为 Head 。
 * 
 * 删除操作
 * 删除现有节点 cur 
 * 1.找到 cur 的上一个结点 prev 及其下一个结点 next ；
 * 2.接下来将 prev 的 next 引用到 cur 的下一个节点 next 。
 * 【注意】在我们的第一步中，我们需要找出 prev 和 next。
 * 使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。
 * 空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。
 * 
 * 删除第一个节点
 * 链表从头结点开始
 * 将下一个节点 分配给 head
 * 
 * 设计链表
 * 在链表类中实现这些功能：
 * get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
 * addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
 * addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
 * addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 * deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
 * 
 * 双指针技巧
 * 1.两个指针【从不同位置出发】，一个从起始段出发，一个从末端开始
 * 2.两个指针【以不同速度移动】，一个指针快一点，一个指针慢一些
 * 【注意】单链表是一个方向上进行遍历连边，适用于第二种场景，快慢指针技巧
 *  环形链表、相交链表、删除链表倒数第N个节点
 * 
 * 环形链表
 * 在链表中使用两个速度不同的指针会遇到的情况
 * 1.如果没有环，快指针将会停在链表的末端
 * 2.如果有环，快指针最终将于慢指针相遇
 * 
 * 
 * 两个指针的速度应该是什么
 * 每次移动【慢指针】【一步】，移动【快指针】【两步】
 * 每次迭代，快指针比慢指针额外移动一步，如果有环，且长度为M，经过M次迭代后，快指针多绕环一周，并赶上慢指针
 * 
 *  双指针技巧小节
 * 1. 在调用 next 字段之前，始终检查节点是否为空。
 * 2. 仔细定义循环的结束条件。
 * 如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 O(1)
 * 如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
 * 如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。
 * 因此，该算法的时间复杂度总共为 O(N)。
 * 
 * 反转链表
 * 一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部
 * 时间复杂度O（N），空间复杂度O（1）
 * 
 * 
 * 
 */
//简单的单链表中节点的定义
//public class SinglyListNode
//{
//    int val; //该节点的值
//    SinglyListNode next; //下一个节点的引用
//    SinglyListNode(int x) { val = x; } //构造函数赋值
//}



using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

namespace LeetCode.LinkedList
{
    public class LinkedListQuestion : MonoBehaviour
    {
        //19. 删除链表的倒数第N个节点（双指针实现）
        //https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
        //方法：快慢指针 
        //指针first遍历全部到最后null节点，second正好指向倒数第n个节点，设置一个哑节点
        public ListNode19 RemoveNthFromEnd(ListNode19 head, int n)
        {
            ListNode19 dummy = new ListNode19(0, head);
            ListNode19 first = head;
            ListNode19 second = dummy;
            for (int i = 0; i < n; i++) //先开始循环n个节点
            {
                first = first.next;
            }
            while (first != null) //first和second一起循环，知道first的节点是null为止
            {
                first = first.next;
                second = second.next;
            }
            second.next = second.next.next;
            ListNode19 ans = dummy.next; //返回头结点
            return ans;
        }

        //21. 合并两个有序链表
        //https://leetcode-cn.com/problems/merge-two-sorted-lists/
        //方法：迭代,一个循环
        //设立一个开头节点dummy，指针prev，调整它的next指针，直到了l1和l2指针指向null
        public ListNode21 MergeTwoLists(ListNode21 l1, ListNode21 l2)
        {
            ListNode21 prehead = new ListNode21(-1);//开头预设节点
            ListNode21 prev = prehead;//指针
            while (l1 != null && l2 != null) //不为空就一直循环
            {
                if (l1.val < l2.val)
                {
                    prev.next = l1;
                    l1 = l1.next;//下一个节点
                }
                else
                {
                    prev.next = l2;
                    l2 = l2.next; //下一个节点
                }
                prev = prev.next; //prev指针移动
            }
            prev.next = l1 == null ? l2 : l1; // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
            return prehead.next;
        }

        //141. 环形链表1(哈希表实现) 时间复杂度O（N），空间复杂度O(N)哈表表插入的开销
        //https://leetcode-cn.com/problems/linked-list-cycle/
        //方法一：哈希表HashSet
        //方法二：快慢指针
        public bool HasCycle1(ListNode head)
        {
            HashSet<ListNode> seen = new HashSet<ListNode>();
            while (head != null)
            {
                if (!seen.Add(head)) //不能在添加进新节点
                {
                    return true;
                }
                head = head.next;
            }
            return false;
        }

        /// <summary>
        /// 141. 环形链表1(快慢指针实现) 时间复杂度O（N），空间复杂度O（1）
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public bool HasCycle2(ListNode head)
        {
            if (head == null || head.next==null) //无效情况 
                return false;
            ListNode slow = head ;
            ListNode fast = head.next;
            while (slow != fast) 
            {
                if (fast==null || fast.next==null) //末尾没有引用节点
                    return false;
                slow = slow.next;
                fast = fast.next.next; //快指针额外多走一步
            }
            return true;
        }

        /// <summary>
        /// 142.环形链表Ⅱ
        /// 方法一：哈希表：先遍历节点，就可以判定链表中存在环
        /// 方法二：快慢指针；慢指针在第一圈一定会和快指针相遇
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode DetectCycle(ListNode head)
        {
            if (head==null) return null; //无效情况
            ListNode slow=head;
            ListNode fast=head;
            while (fast!=null)
            {
                slow = slow.next;
                if (fast.next!=null)
                    fast = fast.next.next;
                else
                    return null;
                if (fast ==slow)
                {
                    ListNode ptr = head;
                    while (ptr!=slow)
                    {
                        ptr = ptr.next;
                        slow = slow.next;
                    }
                    return ptr;
                }
            }
            return null;
        }

        //160. 相交链表（哈希实现）
        //https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
        //题解：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode/
        //算法：哈希表法，时间复杂度0（M+N）， 空间复杂度O（M）
        //遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点 bi 是否在哈希表中。若在，则 bi为相交节点
        //更好的方法是双指针法：不需要额外的空间 while(pa!=pb)
        public ListNode GetIntersectionNode1(ListNode headA, ListNode headB)
        {
            HashSet<ListNode> hash = new HashSet<ListNode>();
            ListNode currA = headA;
            ListNode currB = headB;

            while (currA !=null)
            {
                hash.Add(currA);
                currA = currA.next;
            }

            while (currB!=null)
            {
                if (hash.Contains(currB))
                {
                    return currB;
                }
                currB = currB.next;              
            }
            return null;
        }

        /// <summary>
        /// 160. 相交链表（双指针）
        /// </summary>
        public ListNode GetIntersectionNode2(ListNode headA, ListNode headB)
        {
            if (headA == null || headB == null) return null;//无效情况
            ListNode pA = headA;
            ListNode pB = headB;

            while (pA != pB) //相交，或者都为NULL
            {
                pA = pA == null ? headB : pA.next;
                pB = pB == null ? headA : pB.next;
            }
            return pA;
        }

        //206. 反转链表（迭代双指针实现）
        //https://leetcode-cn.com/problems/reverse-linked-list/
        //方法一：迭代双指针，先画图在做程序
        //方法二：递归，思想就是两个进行交换
        public ListNode206 ReverseList1(ListNode206 head)
        {
            ListNode206 curr = head;
            ListNode206 prev = null;
            ListNode206 nextNode;
            while (curr!=null)
            {
                nextNode = curr.next; //先保存下一個節點
                curr.next = prev; //將當前节点指向prev节点
                //----处理下一个节点---
                prev = curr;
                curr = nextNode;
            }
            return prev;
        }

        public ListNode206 ReverseList2(ListNode206 head)
        {
            if (head == null || head.next == null)
            {
                return head;
            }
            ListNode206 newHead = ReverseList2(head.next); //一直递归直到最后一个
            head.next.next = head; //节点head.next的next指向上一个节点head
            head.next = null;   //将节点head置为空，置为null
            return newHead;     //返回新的头节点
        }

        //234. 回文链表
        //https://leetcode-cn.com/problems/palindrome-linked-list/
        //方法：先存储进list，在用双指针判断
        public bool IsPalindrome(ListNode1 head)
        {
            List<int> vals = new List<int>();

            // 将链表的值复制到数组中
            ListNode1 currentNode = head;
            while (currentNode != null)
            {
                vals.Add(currentNode.val);
                currentNode = currentNode.next;
                vals.Where(a => a == 3).FirstOrDefault();
            }

            // 使用双指针判断是否回文
            int front = 0;
            int back = vals.Count - 1;
            while (front < back)
            {
                if (vals[front] != vals[back])
                {
                    return false;
                }
                front++;
                back--;
            }
            return true;
        }

        //234.回文链表（快慢指针实现）
        //思路：
        //1.找到链表的前半部分的尾结点：使用快慢指针，找到中间位置
        //2.反转后半部分
        //3.判断是否回文
        //4.恢复链表
        //5.返回结果
        //时间复杂度O（N），空间复杂度O（1）
        public bool IsPalindrome2(ListNode1 head)
        {
            if (head == null) return false;

            //1.找到前半部分尾结点
            ListNode1 fast = head;
            ListNode1 slow = head;
            while (fast.next!=null && fast.next.next!=null)
            {
                fast = fast.next.next; //走2步
                slow = slow.next; //走1步
            }
            ListNode1 endOfFistHalf = slow;

            //2.后半部分进行反转，获取第二部分个头结点
            ListNode1 prev = null;
            ListNode1 cur = endOfFistHalf.next;
            ListNode1 nextTemp;
            while (cur!=null)
            {
                nextTemp = cur.next; //临时数据
                cur.next = prev;
                prev = cur;
                cur = nextTemp;
            }
            ListNode1 secondOfHalfStart = prev;

            //3、判断回文：比较两个值
            ListNode1 p1 = head;
            ListNode1 p2 = secondOfHalfStart;
            while (p1 != null && p2!=null)
            {
                if (p1.val!=p2.val)
                {
                    return false;
                }
                else
                {
                    p1 = p1.next;
                    p2 = p2.next;
                }
            }

            //4、还原链表：这步重复第2步操作
            //5、返回结果
            return true;

        }

        //237. 删除链表中的节点
        //https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
        //方法：修改之前next指针跳过要删除的节点，指向后面一个节点
        //注意下一个节点为空的情况，但题目已注明非末尾节点
        public void DeleteNode(ListNode237 node) //需要删除node
        {
            node.val = node.next.val;
            node.next = node.next.next;
        }

        //剑指 Offer 18. 删除链表的节点
        //
        //注意边界问题，头部删除，尾部删除
        public ListNode DeleteNode2(ListNode head, int val)
        {
            if (head.val == val) return head.next; //如果删除的是第一个
            ListNode pre = head;
            ListNode cur = head.next; //2个变量
            while (cur != null && cur.val != val) //如果不是最后一个或者值不相等，处理下一个数据
            {
                pre = cur; 
                cur = cur.next;
            }
            if (cur != null) pre.next = cur.next; //值相等情况下
            return head;
        }

        //203. 移除链表元素(迭代实现)
        //实现方式1：迭代，哑节点
        //时间复杂度：O（N），空间复杂度O（1）
        //https://leetcode-cn.com/problems/remove-linked-list-elements/
        public ListNode RemoveElements(ListNode head, int val)
        {
            if (head == null) return null; //无效情况
            ListNode dummyNode = new ListNode(0); //先定义一个哑节点
            dummyNode.next = head;
            ListNode tempNode = dummyNode;

            while (tempNode.next !=null ) 
            {
                if (tempNode.next.val==val) 
                {
                    tempNode.next = tempNode.next.next; //跳过此节点
                }
                else
                {
                    tempNode = tempNode.next; //不跳过此节点
                }
            }
            return dummyNode.next;
        }

        //203. 移除链表元素（递归实现）
        //时间复杂度O（N） 空间复杂度O（N）
        public ListNode RemoveElements2(ListNode head, int val)
        {
            if (head == null) return head;
            head.next = RemoveElements2(head.next,val);
            return head.val == val ? head.next : head;
        }

        //328. 奇偶链表（分离后进行合并）
        //空间复杂度应为 O(1)，时间复杂度应为 O(nodes) 
        //https://leetcode-cn.com/problems/odd-even-linked-list/
        public ListNode19 OddEvenList(ListNode19 head)
        {
            if (head == null) return null;

            ListNode19 evenHead = head.next;//偶数的头节点
            ListNode19 odd = head , even = evenHead;

            while (even!=null && even.next!=null)
            {
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next; 
                even = even.next;
            }
            odd.next = even;
            return odd;
        }


        //234. 回文链表（快慢指针实现）
        //找到前半部分链表的尾节点。
        //反转后半部分链表。
        //判断是否回文。
        //恢复链表。
        //返回结果。
        //https://leetcode-cn.com/problems/palindrome-linked-list/
        //public bool isPalindrome(ListNode head)
        //{ 

        //}



    }

    //Definition for singly-linked list.
    public class ListNode237
    {
        public int val;
        public ListNode237 next; //下一个节点
        public ListNode237(int x) { val = x; }
    }

    //适用于19、328
    public class ListNode19
    {
        public int val;
        public ListNode19 next;
        public ListNode19(int val = 0, ListNode19 next = null)  //下一个节点的信息
        {
            this.val = val;
            this.next = next;
        }
    }

    public class ListNode206
    {
        public int val;
        public ListNode206 next;
        public ListNode206(int x) { val = x; }
    }

    public class ListNode21
    {
        public int val;
        public ListNode21 next;
        public ListNode21(int val = 0, ListNode21 next = null)
        {
            this.val = val;
            this.next = next;
        }
    }

    public class ListNode1
    {
        public int val;
        public ListNode1 next;
        public ListNode1(int x) { val = x; }
    }
    
    /// <summary>
    /// 适用于707
    /// </summary>
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val) { this.val = val;}
    }

    //707设计链表（单链表实现）
    //https://leetcode-cn.com/problems/design-linked-list/
    public class MyLinkedList1
    {
        int size;
        public ListNode head;

        /** Initialize your data structure here. */
        public MyLinkedList1()
        {
            size = 0;
            head = new ListNode(0);
        }

        /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
        public int Get(int index)
        {
            if (index < 0 || index >= size) { return -1; } //无效情况
            ListNode cur = head;
            for (int i = 0; i < index+1; i++) //注意边界
            {
                cur = cur.next; //移动到下一个节点
            }
            return cur.val;
        }

        /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
        public void AddAtHead(int val)
        {
            AddAtIndex(0, val);
        }

        /** Append a node of value val to the last element of the linked list. */
        public void AddAtTail(int val)
        {
            AddAtIndex(size, val);
        }

        /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
        public void AddAtIndex(int index, int val)
        {
            if (index > size) return; //无效情况
            if (index < 0) index = 0;

            size++; //链表容量+1

            ListNode prev = head;
            for (int i = 0; i < index; i++) prev = prev.next;
            ListNode newNode = new ListNode(val);
            newNode.next = prev.next;
            prev.next = newNode;
        }

        /** Delete the index-th node in the linked list, if the index is valid. */
        public void DeleteAtIndex(int index)
        {
            if (index >= size) return; //无效情况
            if (index < 0) return;

            size--; //链表容量+1
            ListNode prev = head;
            for (int i = 0; i < index; i++) prev = prev.next;
            prev.next = prev.next.next;
        }
    }

    //707设计链表（双链表实现）
    //https://leetcode-cn.com/problems/design-linked-list/
    public class MyLinkedList2
    {
        /** Initialize your data structure here. */
        public MyLinkedList2()
        {

        }

        /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
        public int Get(int index)
        {
            return -1;
        }

        /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
        public void AddAtHead(int val)
        {

        }

        /** Append a node of value val to the last element of the linked list. */
        public void AddAtTail(int val)
        {

        }

        /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
        public void AddAtIndex(int index, int val)
        {

        }

        /** Delete the index-th node in the linked list, if the index is valid. */
        public void DeleteAtIndex(int index)
        {

        }
    }


}